package l.l.w.Instruction2Algorithm.MaximumSubarray;

/**
 * Created by llw on 2017/8/31.
 */
public class MaximumSubarray {

    /**
     * 使用递归的方式进行（未测试）
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public Result findMaxSubarray(int[] arr,int low, int high){
        if(low >= high)
            return new Result(arr[low],low,high);
        int mid = low+(high-low+1)/2;
        Result subResult1 = findMaxSubarray(arr, low, mid);
        Result subResult2 = findMaxSubarray(arr, mid + 1, high);
        Result subResult3=findMaxSubAcrossMid(arr,low,mid,high);
        if(subResult1.result>subResult2.result && subResult1.result > subResult3.result)
            return  subResult1;
        else if(subResult2.result> subResult1.result && subResult2.result > subResult3.result )
            return  subResult2;
        else
            return  subResult3;
    }


    private Result findMaxSubAcrossMid(int[] arr, int low, int mid, int high) {
        int sum=0;
        int leftIndex = mid;
        int leftsum=arr[low];
        for(int i = mid; i >=low;--i){
            sum +=arr[i];
            if(sum >=leftsum){
                leftsum = sum;
                leftIndex = i;
            }
        }
        sum=0;
        int rightIndex = mid;
        int rightsum=Integer.MIN_VALUE;
        for(int i = mid; i <=high;++i){
            sum +=arr[i];
            if(sum >=rightsum){
                rightsum = sum;
                rightIndex = i;
            }
        }
        if(leftsum+rightsum < leftsum)
            return new Result(rightsum,mid,mid);
        return new Result(leftsum+rightsum,leftIndex,rightIndex);
    }


    /**
     *
     * @param arr
     * @return
     */
    public Result findMaxSubarray2(int[] arr){
        int low=0,high=0;
        int tempLow=0;
        int maxSum = Integer.MIN_VALUE;
        int sum=0;
        for(int i =0 ; i < arr.length;++i){
            sum+=arr[i];
            if(sum >= maxSum){
                maxSum = sum;
                low = tempLow;
                high=i;
            }
            if(sum<0){
                sum = 0;
                tempLow =i+1;
            }
        }
        return new Result(maxSum,low,high);
    }

    public static void main(String[] args) {
        int[] a = {-5,-4,2,3,4,5,6,-3,-1,10,9};
        Result res = new MaximumSubarray().findMaxSubarray2(a);
        System.out.println(res.result+" a["+res.low+","+res.high+"]");
    }
}
class Result{
    int result;
    int high;
    int low;
    Result(){

    }
    Result(int result,int low, int high){
        this.high=high;
        this.low = low;
        this.result = result;
    }
}